package swardToOffer.abstractModeling;

/**
 * @Author ChanZany
 * @Date 2021/5/27 11:22
 * @Version 1.0
 * 面试题62：圆圈中最后剩下的数字
 * 题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里
 * 删除第m个数字。求出这个圆圈里剩下的最后一个数字。
 * [分析]:这是典型的约瑟夫环问题,对于约瑟夫环问题,最直观的解法就是构造或模拟环形链表来对圆圈进行建模,除此之外,通过数学分析也可以得到递归解
 * 1. 数组解法
 * 2. 循环链表
 * 3. 递归解法
 *
 * 我们有n个数，下标从0到n-1，然后从index=0开始数，每次数m个数，最后看能剩下谁。我们假设能剩下的数的下标为y，则我们把这件事表示为
 * f(n,m) = y,我们假设f(n-1,m)=x，然后来找一找f(n,m)和f(n-1,m)到底啥关系。
 * 因为要从0数m个数，那最后肯定落到了下标为m-1的数身上了，但这个下标可能超过我们有的最大下标（n-1）了。所以攒满n个就归零接着数，逢n归零，所以要模n,
 * 所以有n个数的时候，我们划掉了下标为(m-1)%n的数字。
 * 我们划完了这个数，往后数x+1下,它下标肯定变成了(m-1)%n +x+1，和第一步的想法一样，你肯定还是得取模，所以答案为[(m-1)%n+x+1]%n，则
 * f(n,m)=[(m-1)%n+x+1]%n,由于(a+b)%c=((a%c)+(b%c))%c,a%c=(a%c)%c
 * 所以化简结果为 f(n,m) = (m+f(n-1,m))%n,当n=1时,剩余的下标只能是0,即f(1,m)=0;
 */

class Node {
    int val;//该节点的编号
    Node next;//该节点的下一个节点

    public Node(int data, Node next) {
        this.next = next;
        this.val = data;
    }

    public Node(int data) {
        this.val = data;
    }

    public Node() {

    }
}

public class LastNumberInCircle {


    public int lastRemaining(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = lastRemaining(n - 1, m);
        return (m + x) % n;
    }

    public int solution2(int n, int m) {
        /*构建循环链表*/
        Node head = new Node(0);
        Node p = head;
        for (int i = 1; i < n; i++) {
            p.next = new Node(i);
            p = p.next;
        }
        p.next = head;
        /*剔除出局结点*/
        p = head;
        Node tmp = null;
        while (p.next != p) {
            //报数
            for (int i = 1; i < m; i++) {
                tmp = p;
                p = p.next;
            }
            tmp.next = p.next;
            p = p.next;
        }
        return p.val;
    }

    public int solution1(int n, int m) {
        int[] out = new int[n];//out[i]表示下标i的人已出局
        int cnt = 0, i = 0, k = 0;//cnt为已出局人数,i为数组下标,k为报数下标
        while (cnt != n) {
            if (i >= n) i = 0;//数据下标越界就回到0
            if (out[i] == 0) {//跳过已出局的进行报数
                k++;
                if (k == m) {
                    out[i] = 1;
                    cnt++;
                    k = 0;//重新报数
                }
            }
            i++;
        }
        return i - 1;
    }


    public static void main(String[] args) {
        LastNumberInCircle Main = new LastNumberInCircle();
        System.out.println(Main.lastRemaining(5, 3));
    }
}
